package com.job.DQH.dqh719.homework;

import java.util.*;

//利用两个栈对数组进行排序
public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入数组长度");
        int length = sc.nextInt();//读取用户输入，设置数组长度length

        List<Integer> list = new LinkedList<>();

        while (list.size()<length){//生成未排序的原数组，利用random类
            Random ran = new Random();
            list.add(ran.nextInt(1000));
        }

        System.out.println("你生成的原数组为："+list);

        Stack<Integer> finalStack = new Stack<>();//最终栈
        Stack<Integer> tempStack = new Stack<>();//中转栈

        int i = 0;

        while (i<list.size()){//由于需要对length个数排序，故循环length次，也就是list.size次
            int temp = list.get(i);
            sort(finalStack,tempStack,temp);
            i++;
        }

        for (int j = 0; j <list.size() ; j++) {
            list.set(j,finalStack.pop());
        }

        System.out.println("经过降序排序，现在数组为："+list);

    }

    public static void sort(Stack<Integer> finalStack,Stack<Integer> tempStack,Integer temp){

        while (!finalStack.isEmpty() && finalStack.peek()>=temp){
            tempStack.push(finalStack.pop());
        }

        finalStack.push(temp);

        while (!tempStack.isEmpty()){
            finalStack.push(tempStack.pop());
        }

    }

}
